package m202405.d16;

import java.util.Arrays;

/**
 * @@author: 爱做梦的锤子
 * @date: 2024/5/16 15:42
 */
public class Q322 {

    public static void main(String[] args) {
        Q322 q322 = new Q322();
        q322.coinChange(new int[]{3}, 4);
    }

    //coins = [2,3,5]; amount = 12
    //f(12) = min(f(12-2),f(12-3),f(12-5))+1;
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            dp[i] = findMin(dp, coins, i) + 1;
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }

    private int findMin(int[] dp, int[] coins, int amount) {
        int min = dp[amount];
        for (int coin : coins) {
            int index = amount - coin;
            if (index < 0) {
                continue;
            }
            min = Math.min(min, dp[index]);
        }
        return min;
    }
}
